// 给一个字符串数字，删除k位，让这个数字最小

#include <iostream>
#include <string>
#include <vector>

std::string removeKdigits(std::string num, int k)
{
    int n = num.size();
    if (n <= k)
        return "0";

    int i = 0;
    while (k > 0 && i < n - 1)
    {
        // 后小，删自己
        if (num[i] > num[i + 1])
        {
            num.erase(i, 1);
            k--;
            // 更新处理位置
            if (i != 0)
                i--;
        }
        // 递增或相同不变
        else
        {
            i++;
        }
    }

    // 如果没处理完毕
    if (k > 0)
    {
        num.erase(num.end() - k, num.end());
    }

    // 找到不等于0的位置
    auto it = num.begin();
    while (it != num.end())
    {
        if (*it != '0')
            break;
        it++;
    }

    std::string ret(it, num.end());

    return ret.size() == 0 ? "0" : ret;
}

// 栈不一定非要用stack，也可以用vector。
// 如果说对于栈以后想把站内元素转化成一个string，那么就使用vetcor
std::string removeKdigits(std::string num, int k)
{
    std::vector<char> st;
    for (int i = 0; i < num.size(); i++)
    {
        while (st.size() > 0 && st.back() > num[i] && k > 0)
        {
            st.pop_back();
            k--;
        }
        st.push_back(num[i]);
    }

    // 删除后k个元素
    st.erase(st.end() - k, st.end());
    // 找到第一个非0位置
    auto it = st.begin();
    while (it != st.end())
    {
        if (*it != '0')
            break;
        it++;
    }
    std::string ret(it, st.end());

    return ret.size() == 0 ? "0" : ret;
}